/**
 * Created with IntelliJ IDEA
 * Description:
 * User: Administrator
 * Data: 2023 - 07 - 17
 * Time: 11:45
 */
//法一：重复计算的次数过多
class Solution1 {
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        int leftChildHeight = getHeight(root.left);
        int rightChildHeight = getHeight(root.right);
        if(Math.abs(leftChildHeight - rightChildHeight) <= 1 && isBalanced(root.left) && isBalanced(root.right)) {
            return true;//注意是二叉树的每个节点的左右两个子树的高度差的绝对值不超过1，注意是每个节点，所以要递归isBalanced
        }
        return false;
    }
    int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        return (leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1);
    }
}

//法二：
class Solution2 {
    public boolean isBalanced(TreeNode root) {
        if(root == null) {
            return true;
        }
        return getHeight(root) >= 0;
    }
    private int getHeight(TreeNode root) {
        if(root == null) {
            return 0;
        }
        int leftHeight = getHeight(root.left);
        int rightHeight = getHeight(root.right);
        if(leftHeight >= 0 && rightHeight >= 0 && Math.abs(leftHeight - rightHeight) <= 1) {//上面的leftHeight和rightHeight有可能都返回-1，这时leftHeight-rightHeight的绝对值<=1，所以要加上leftHeight>=0&&rightHeight>=0的条件
            return Math.max(leftHeight, rightHeight) + 1;
        }
        return -1;
    }
}

